#include "lib.h"

void swap(void* p1, void* p2, size_t data_size) {
    void* tmp = malloc(data_size);
    memcpy(tmp, p1, data_size);
    memcpy(p1, p2, data_size);
    memcpy(p2, tmp, data_size);
    free(tmp);
}

size_t partition(void* data, size_t total_size, size_t data_size, int (*compare)(const void*, const void*)) {
    if(total_size <= 1) {
        return 0;
    }

    srand((unsigned)time(0));
    size_t pivot_offset = rand()%total_size;;
    void* pivot = data+(pivot_offset)*data_size;
    swap(data, pivot, data_size);
    pivot = data;

    void* iter = data+data_size;
    size_t iter_offset = 1;
    size_t pos = 1; // left the pos will smaller(bigger) than pivot(exclude)

    while(iter_offset < total_size) {
        if(compare(pivot, iter)) {
            // pivot <= iter
            swap(iter, pivot+pos*data_size, data_size);
            pos++;
        } else {
        }
        iter += data_size;
        iter_offset++;
    }
    pos--;
    swap(pivot, pivot+pos*data_size, data_size);
    return pos;
}

void qsort(void* data, size_t total_size, size_t data_size, int (*compare)(const void*, const void*)) {
    if(total_size <= 1) {
        return ;
    }
    
    size_t pos = partition(data, total_size, data_size, compare);
    qsort(data, pos, data_size, compare);
    qsort(data+(pos+1)*data_size, total_size-pos-1, data_size, compare);
}
